/*
 * @lc app=leetcode.cn id=20 lang=cpp
 *
 * [20] 有效的括号
 *
 * https://leetcode-cn.com/problems/valid-parentheses/description/
 *
 * algorithms
 * Easy (44.53%)
 * Likes:    3134
 * Dislikes: 0
 * Total Accepted:    1M
 * Total Submissions: 2.3M
 * Testcase Example:  '"()"'
 *
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
 * 
 * 有效字符串需满足：
 * 
 * 
 * 左括号必须用相同类型的右括号闭合。
 * 左括号必须以正确的顺序闭合。
 * 
 * 
 * 
 * 
 * 示例 1：
 * 
 * 
 * 输入：s = "()"
 * 输出：true
 * 
 * 
 * 示例 2：
 * 
 * 
 * 输入：s = "()[]{}"
 * 输出：true
 * 
 * 
 * 示例 3：
 * 
 * 
 * 输入：s = "(]"
 * 输出：false
 * 
 * 
 * 示例 4：
 * 
 * 
 * 输入：s = "([)]"
 * 输出：false
 * 
 * 
 * 示例 5：
 * 
 * 
 * 输入：s = "{[]}"
 * 输出：true
 * 
 * 
 * 
 * 提示：
 * 
 * 
 * 1 
 * s 仅由括号 '()[]{}' 组成
 * 
 * 
 */

// @lc code=start
class Solution {
public:
    bool isValid(string s) {
        // stack<char> st;
        // int size = s.size();
        // if(size % 2) return false;
        // for(int i = 0; i < s.size(); i++){
        //     if(s[i] == '[') st.push('[');
        //     else if(s[i] == '{') st.push('{');
        //     else if(s[i] == '(') st.push('(');
        //     else if(s[i] == '}') {
        //         if(st.empty()  || st.top() != '{') return false;
        //         st.pop();
        //     }
        //     else if(s[i] == ']') {
        //         if(st.empty()  || st.top() != '[') return false;
        //         st.pop();
        //     }
        //     else if(s[i] == ')') {
        //         if(st.empty()  || st.top() != '(') return false;
        //         st.pop();
        //     }
        // } 
        // if(!st.empty()) return false;
        // return true;



        stack<int> st;

        for(int i = 0; i < s.size(); i++){
            if(s[i] == '[') st.push(']');
            else if(s[i] == '{') st.push('}');
            else if(s[i] == '(') st.push(')');
            else if(st.empty() || s[i] != st.top()) return false;
            else st.pop();
        }
        // if(!st.empty()) return false;
        // return true;
        return st.empty();
    }
};
// @lc code=end

